home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / sos3-2.lha / src / agg / List.c < prev    next >
C/C++ Source or Header  |  1992-01-23  |  20KB  |  663 lines
  1. /* --------------------------------------------------------------------------
  2.  * Copyright 1992 by Forschungszentrum Informatik (FZI)
  3.  *
  4.  * You can use and distribute this software under the terms of the licence
  5.  * you should have received along with this program.
  6.  * If not or if you want additional information, write to
  7.  * Forschungszentrum Informatik, "STONE", Haid-und-Neu-Strasse 10-14,
  8.  * D-7500 Karlsruhe 1, Germany.
  9.  * --------------------------------------------------------------------------
  10.  */
  11. // **************************************************************************
  12. // Module List                      03/07/89           Bernhard Schiefer (bs)
  13. //                                                   modified : 24/10/91 (bs)
  14. // **************************************************************************
  15. // implements methods of classes: List, sos_List_node
  16. // **************************************************************************
  17.  
  18. #include "sys.h"
  19. #include "agg_err.h"
  20. #include "trc_agg.h"
  21.  
  22. #include "agg_sos.h"
  23.  
  24. // **************************************************************************
  25. void sos_Object_List::local_initialize (sos_Object_List list)
  26. // **************************************************************************
  27. {  T_PROC ("sos_Object_List::local_initialize");
  28.    TT (agg_H, T_ENTER);
  29.  
  30.    list.set_first (sos_List_node::make (NO_OBJECT));
  31.    list.set_last (sos_List_node::make (NO_OBJECT));
  32.    list.set_cardinality (0);
  33.  
  34.    TT (agg_H, T_LEAVE);
  35. } // ** local_initialize **
  36.  
  37. // **************************************************************************
  38. void sos_Object_List::local_finalize (sos_Object_List list)
  39. // **************************************************************************
  40. {  T_PROC ("sos_Object_List::local_finalize");
  41.    TT (agg_H, T_ENTER);
  42.  
  43.    list.clear();
  44.  
  45.    TT (agg_H, T_LEAVE);
  46. } // ** local_finalize **
  47.  
  48. // **************************************************************************
  49. void sos_Object_List::append (sos_Object o)
  50. // **************************************************************************
  51. // append an element
  52. {
  53.    T_PROC ("sos_Object_List::append");
  54.    TT (agg_H, T_ENTER);
  55.  
  56.    sos_List_node cn;
  57.    cn = sos_List_node::create (self.container());
  58.    cn.set_val (o);
  59.  
  60.    if (self.get_first() == NO_OBJECT)          // insert the first node
  61.    {  self.set_first (cn);
  62.       self.set_last  (cn);
  63.       cn.set_succ (sos_List_node::make (NO_OBJECT));
  64.       cn.set_pred (sos_List_node::make (NO_OBJECT));
  65.    }
  66.    else
  67.    {  sos_List_node n = self.get_last();
  68.       n.insert_after (cn); 
  69.       self.set_last (cn);
  70.    }
  71.  
  72.    self.set_cardinality (self.get_cardinality() + 1);
  73.  
  74.    TT (agg_H, T_LEAVE);
  75. } // ** append **
  76.  
  77. // **************************************************************************
  78. void sos_Object_List::insert (Index  position, sos_Object o)
  79. // **************************************************************************
  80. // insert an element at the specified position
  81. // if position 0 is specified insert after the last element
  82. {
  83.    T_PROC ("sos_Object_List::insert");
  84.    TT (agg_H, T_ENTER; TI (position));
  85.  
  86.    err_assert (position >= 0, "sos_Object_List::insert");
  87.  
  88.    if (position > self.get_cardinality())
  89.       position = 0;        // insert after last!
  90.  
  91.    if (position == 0)
  92.       self.append (o);
  93.    else
  94.    {  sos_List_node first_node = self.get_first();
  95.       sos_List_node cn = sos_List_node::create (self.container());
  96.       cn.set_val (o);
  97.       if (first_node == NO_OBJECT)              // insert the first node 
  98.       {  self.set_first (cn);
  99.          self.set_last (cn);
  100.      cn.set_succ (sos_List_node::make (NO_OBJECT));
  101.      cn.set_pred (sos_List_node::make (NO_OBJECT));
  102.       }
  103.       else
  104.       {  sos_List_node n = first_node.succ (position - 1);
  105.          n.insert_before (cn);
  106.          if (position == 1) self.set_first (cn);
  107.       } 
  108.       self.set_cardinality (self.get_cardinality() + 1);
  109.    }
  110.    TT (agg_H, T_LEAVE);
  111.  
  112. } // ** insert **
  113.  
  114. // **************************************************************************
  115. void sos_Object_List::remove (Index  position)
  116. // **************************************************************************
  117. {
  118.    T_PROC ("sos_Object_List::remove");
  119.    TT (agg_H, T_ENTER);
  120.  
  121.    sos_List_node first_node = self.get_first();
  122.    err_assert (first_node != NO_OBJECT, "sos_Object_List::remove");
  123.  
  124.    sos_List_node cn = first_node.succ (position - 1);
  125.    err_assert (cn != NO_OBJECT, "sos_Object_List::remove");
  126.  
  127. #ifdef ATT
  128.    if (cn.operator==(first_node))
  129.       self.set_first (first_node.succ());
  130.    if (cn.operator==(self.get_last()))
  131.       self.set_last (self.get_last().pred());
  132. #else
  133.    if (cn == first_node)
  134.       self.set_first (first_node.succ());
  135.    if (cn == self.get_last())
  136.       self.set_last (self.get_last().pred());
  137. #endif
  138.  
  139.    cn.remove(); 
  140.    self.set_cardinality (self.get_cardinality() - 1);
  141.  
  142.    TT (agg_H, T_LEAVE);
  143.  
  144. } // ** remove **
  145.  
  146. // **************************************************************************
  147. sos_Object sos_Object_List::get_nth (Index pos)
  148. // **************************************************************************
  149. {
  150.    T_PROC ("sos_Object_List::get_nth");
  151.    TT (agg_H, T_ENTER; TI (pos));
  152.     
  153.    sos_List_node cn = self.get_first();
  154.    err_assert (cn != NO_OBJECT, "sos_Object_List::get_nth");
  155.  
  156.    cn = cn.succ (pos - 1);
  157.  
  158.    err_assert (cn != NO_OBJECT, "sos_Object_List::get_nth");
  159.  
  160.    sos_Object o = cn.get_val();
  161.  
  162.    TT (agg_H, T_LEAVE);
  163.    return o;
  164. } // ** get_nth **
  165.  
  166. // **************************************************************************
  167. void sos_Object_List::set_nth (Index pos, sos_Object o)
  168. // **************************************************************************
  169. // the value of the sos_Object at Index position is replaced by o
  170. {
  171.    T_PROC ("sos_Object_List::set_nth");
  172.    TT (agg_H, T_ENTER; TI (pos));
  173.  
  174.    sos_List_node cn = self.get_first();
  175.    err_assert (cn != NO_OBJECT, "sos_Object_List::set_nth");
  176.  
  177.    cn = cn.succ (pos - 1);
  178.    err_assert (cn != NO_OBJECT, "sos_Object_List::set_nth");
  179.  
  180.    cn.set_val (o);
  181.  
  182.    TT (agg_H, T_LEAVE);
  183.  
  184. } // ** set_nth **
  185.  
  186. // **************************************************************************
  187. void sos_Object_List::operator+= (sos_Object_List alist)
  188. // **************************************************************************
  189. {
  190.    T_PROC ("sos_Object_List::operator+=");
  191.    TT (agg_H, T_ENTER);
  192.  
  193.    for (sos_List_node cn = alist.get_first();
  194.         (cn != NO_OBJECT);
  195.         (cn = cn.succ()))
  196.       self.append (cn.get_val());
  197.  
  198.    TT (agg_H, T_LEAVE);
  199. } // ** operator+= **
  200.  
  201. // **************************************************************************
  202. Index sos_Object_List::current_pos (sos_Cursor c)
  203. // **************************************************************************
  204. {
  205.    T_PROC ("sos_Object_List::current_pos");
  206.    TT (agg_H, T_ENTER);
  207.  
  208.    Index result = 0;
  209.  
  210.    err_assert (self.is_valid (c), "sos_Object_List::current_pos");
  211.  
  212.    for (sos_List_node cn = sos_List_node::make (c.get_current());
  213.         (cn != NO_OBJECT);
  214.         (cn = cn.pred()))
  215.       result++;
  216.  
  217.    TT (agg_H, T_LEAVE; TI (result));
  218.    return result;
  219. } // ** current_pos **
  220.  
  221. // **************************************************************************
  222. sos_Bool sos_Object_List::move_cursor (sos_Cursor c, Index position)
  223. // **************************************************************************
  224. {
  225.    T_PROC ("sos_Object_List::move_cursor");
  226.    TT (agg_H, T_ENTER; TI (position));
  227.  
  228.    err_assert (c.defined_for (self), "sos_Object_List::move_cursor");
  229.  
  230.    sos_Bool success = TRUE;
  231.    sos_List_node current = self.get_first();
  232.  
  233.    if (current == NO_OBJECT)
  234.       success = FALSE;
  235.    else
  236.    {  current = current.succ (position - 1);
  237.       if (current != NO_OBJECT)
  238.          c.set_current (current);
  239.       else
  240.      success = FALSE;
  241.    } // else
  242.  
  243.    TT (agg_H, T_LEAVE; TB(success));
  244.    return success;
  245. } // ** move_cursor **
  246.  
  247. // **************************************************************************
  248. void sos_Object_List::insert_before (sos_Cursor c, sos_Object o)
  249. // **************************************************************************
  250. {
  251.    T_PROC ("sos_Object_List::insert_before");
  252.    TT (agg_H, T_ENTER);
  253.  
  254.    err_assert (self.is_valid (c), "sos_Object_List::insert_before");
  255.  
  256.    sos_List_node cn = sos_List_node::create (self.container());
  257.    cn.set_val (o);
  258.    sos_List_node::make (c.get_current()).insert_before (cn);
  259.    self.set_cardinality (self.get_cardinality() + 1);
  260.    if (cn.pred() == NO_OBJECT)
  261.       self.set_first (cn);
  262.  
  263.    TT (agg_H, T_LEAVE);
  264. }
  265.  
  266. // **************************************************************************
  267. void sos_Object_List::insert_after (sos_Cursor c, sos_Object o)
  268. // **************************************************************************
  269. {
  270.    T_PROC ("sos_Object_List::insert_after");
  271.    TT (agg_H, T_ENTER);
  272.  
  273.    err_assert (self.is_valid (c), "sos_Object_List::insert_after");
  274.  
  275.    sos_List_node cn = sos_List_node::create (self.container());
  276.    cn.set_val (o);
  277.    sos_List_node::make (c.get_current()).insert_after (cn);
  278.    self.set_cardinality (self.get_cardinality() + 1);
  279.    if (cn.succ() == NO_OBJECT)
  280.       self.set_last (cn);
  281.  
  282.    TT (agg_H, T_LEAVE);
  283. }
  284.  
  285. // **************************************************************************
  286. void sos_Object_List::local_assign (sos_Object_List x, sos_Object o)
  287. // **************************************************************************
  288. {
  289.    T_PROC ("sos_Object_List::local_assign");
  290.    TT (agg_H, T_ENTER );
  291.  
  292.    sos_Object_List y = sos_Object_List::make (o);
  293.    x.clear();
  294.    x.operator+= (y);
  295.  
  296.    TT (agg_H, T_LEAVE);
  297. } // ** local_assign **
  298.  
  299. // **************************************************************************
  300. sos_Bool sos_Object_List::local_equal (sos_Object_List x,
  301.                        sos_Object      o,
  302.                        sos_Eq_kind     eq_kind)
  303. // **************************************************************************
  304. {
  305.    T_PROC ("sos_Object_List::local_equal");
  306.    TT (agg_H, T_ENTER );
  307.  
  308.    sos_Bool result;
  309.  
  310.    if ((eq_kind EQ EQ_STRONG AND NOT o.has_type (x.type())) OR
  311.        (eq_kind EQ EQ_WEAK   AND NOT o.isa     (x.type())))
  312.       result = FALSE;
  313.    else
  314.    {  sos_Object_List y = sos_Object_List::make (o);
  315.       if (x.get_cardinality() != y.get_cardinality())
  316.      result = FALSE;
  317.       else
  318.       {  result = TRUE;
  319.      sos_Bool based_on_equal = x.get_based_on_equal();
  320.      sos_Int  comp = 0;
  321.      agg_iterate_double (x, sos_Object x_e, y, sos_Object y_e, comp)
  322.      {  result = agg_same_entity (x_e, y_e, based_on_equal, eq_kind);
  323.         if (NOT result) break;
  324.      }
  325.      agg_iterate_double_end (x, x_e, y, y_e, comp);
  326.      result = (sos_Bool)(result AND comp == 0);
  327.       }
  328.    }
  329.  
  330.    TT (agg_H, T_LEAVE; TB(result));
  331.  
  332.    return result;
  333. } // ** local_equal **
  334.  
  335. // **************************************************************************
  336. sos_Int sos_Object_List::local_hash_value (sos_Object_List x)
  337. // **************************************************************************
  338. {
  339.    T_PROC ("sos_Object_List::local_hash_value");
  340.    TT (agg_H, T_ENTER );
  341.  
  342.    sos_Int result;
  343.  
  344.    if (x.is_empty())
  345.       result = 0;
  346.    else
  347.       result = x.get_nth (1).hash_value();
  348.  
  349.    TT (agg_H, T_LEAVE; TB(result));
  350.  
  351.    return result;
  352. } // ** local_hash_value **
  353.  
  354. // **************************************************************************
  355. sos_Object sos_Object_List::get (sos_Cursor c)
  356. // **************************************************************************
  357. {
  358.    T_PROC ("sos_Object_List::get (sos_Cursor)");
  359.    TT (agg_H, T_ENTER);
  360.  
  361.    err_assert (self.is_valid (c), "sos_Object_List::get (sos_Cursor)");
  362.  
  363.    sos_Object o = sos_List_node::make (c.get_current()).get_val();
  364.  
  365.    TT (agg_H, T_LEAVE);
  366.    return o;
  367.  
  368. } // ** get **
  369.  
  370. // **************************************************************************
  371. void sos_Object_List::set (sos_Cursor c, sos_Object o)
  372. // **************************************************************************
  373. {
  374.    T_PROC ("sos_Object_List::set");
  375.    TT (agg_H, T_ENTER);
  376.  
  377.    err_assert (self.is_valid (c), "sos_Object_List::set");
  378.  
  379.    sos_List_node::make (c.get_current()).set_val (o);
  380.  
  381.    TT (agg_H, T_LEAVE);
  382.  
  383. } // ** set **
  384.  
  385. // **************************************************************************
  386. void sos_Object_List::remove_at (sos_Cursor c)
  387. // **************************************************************************
  388. {
  389.    T_PROC ("sos_Object_List::remove_at");
  390.    TT (agg_H, T_ENTER);
  391.  
  392.    err_assert (self.is_valid (c), "sos_Object_List::remove_at");
  393.  
  394.    sos_List_node n = sos_List_node::make (c.get_current());
  395.  
  396. #ifdef ATT
  397.    if (n.operator==(self.get_first()))
  398.       self.set_first (self.get_first().succ());
  399.    if (n.operator==(self.get_last()))
  400.       self.set_last (self.get_last().pred());
  401. #else
  402.    if (n == self.get_first())
  403.       self.set_first (self.get_first().succ());
  404.    if (n == self.get_last())
  405.       self.set_last (self.get_last().pred());
  406. #endif
  407.  
  408.    self.to_succ (c);
  409.    n.remove();
  410.    self.set_cardinality (self.get_cardinality() - 1);
  411.  
  412.    TT (agg_H, T_LEAVE);
  413. } // ** remove_at **
  414.  
  415. // **************************************************************************
  416. sos_Int sos_Object_List::card ()
  417. // **************************************************************************
  418. {
  419.    T_PROC ("sos_Object_List::card");
  420.    TT (agg_H, T_ENTER);
  421.  
  422.    sos_Int crd = self.get_cardinality();
  423.  
  424.    TT (agg_H, T_LEAVE);
  425.    return crd;
  426. } // ** card **
  427.  
  428. // **************************************************************************
  429. sos_Cursor sos_Object_List::open_cursor (sos_Container ct)
  430. // **************************************************************************
  431. {
  432.    // creates a new cursor-object and positions it 
  433.    // to the first element
  434.  
  435.    T_PROC ("sos_Object_List::open_cursor");
  436.    TT (agg_H, T_ENTER);
  437.  
  438.    sos_Cursor new_c = sos_Cursor::create (ct, self);
  439.    new_c.set_current (self.get_first());
  440.  
  441.    TT (agg_H, T_LEAVE);
  442.    return new_c;
  443. } // ** open_cursor **
  444.  
  445. // **************************************************************************
  446. void sos_Object_List::close_cursor (sos_Cursor c)
  447. // **************************************************************************
  448. {
  449.    // The result of any operation using sos_Cursor c
  450.    // is undefined after this operation.
  451.  
  452.    T_PROC ("sos_Object_List::close_cursor");
  453.    TT (agg_H, T_ENTER);
  454.  
  455.    err_assert (c.defined_for (self), "sos_Object_List::close_cursor");
  456.  
  457.    c.destroy();
  458.  
  459.    TT (agg_H, T_LEAVE);
  460. } // ** close_cursor **
  461.  
  462. // **************************************************************************
  463. sos_Cursor sos_Object_List::duplicate (sos_Cursor c)
  464. // **************************************************************************
  465. {
  466.    // creates a new cursor-object for the Aggregate and
  467.    // positions it on the same element as c
  468.  
  469.    T_PROC ("sos_Object_List::duplicate");
  470.    TT (agg_H, T_ENTER);
  471.  
  472.    err_assert (c.defined_for (self), "sos_Object_List::duplicate");
  473.  
  474.    sos_Cursor new_c = sos_Cursor::create (c.container(), self);
  475.    new_c.set_current (c.get_current());
  476.  
  477.    TT (agg_H, T_LEAVE);
  478.    return new_c;
  479. } // ** duplicate **
  480.  
  481. // **************************************************************************
  482. sos_Bool sos_Object_List::is_valid (sos_Cursor c)
  483. // **************************************************************************
  484. {
  485.    T_PROC ("sos_Object_List::is_valid");
  486.    TT (agg_H, T_ENTER);
  487.  
  488.    err_assert (c.defined_for (self), "sos_Object_List::is_valid");
  489.  
  490.    sos_Bool valid = (c.get_current() != NO_OBJECT);
  491.  
  492.    TT (agg_H, T_LEAVE; TB(valid));
  493.    return valid;
  494. } // ** is_valid **
  495.  
  496. // **************************************************************************
  497. sos_Bool sos_Object_List::to_first (sos_Cursor c)
  498. // **************************************************************************
  499. {
  500.    T_PROC ("sos_Object_List::to_first");
  501.    TT (agg_H, T_ENTER);
  502.  
  503.    err_assert (c.defined_for (self), "sos_Object_List::to_first");
  504.  
  505.    sos_List_node first = self.get_first();
  506.    c.set_current (first);
  507.  
  508.    sos_Bool valid = (first != NO_OBJECT);
  509.  
  510.    TT (agg_H, T_LEAVE; TB(valid));
  511.    return valid;
  512. } // ** to_first **
  513.  
  514. // **************************************************************************
  515. sos_Bool sos_Object_List::to_last (sos_Cursor c)
  516. // **************************************************************************
  517. {
  518.    T_PROC ("sos_Object_List::to_last");
  519.    TT (agg_H, T_ENTER);
  520.  
  521.    err_assert (c.defined_for (self), "sos_Object_List::to_last");
  522.  
  523.    sos_List_node last = self.get_last();
  524.    c.set_current (last);
  525.  
  526.    sos_Bool valid = (last != NO_OBJECT);
  527.  
  528.    TT (agg_H, T_LEAVE; TB(valid));
  529.    return valid;
  530. } // ** to_last **
  531.  
  532. // **************************************************************************
  533. sos_Bool sos_Object_List::to_succ (sos_Cursor c, sos_Int i)
  534. // **************************************************************************
  535. {
  536.    // Move the sos_Cursor to the i-th successing element
  537.    // The function returns FALSE if no such element exists.
  538.  
  539.    T_PROC ("sos_Object_List::to_succ");
  540.    TT (agg_H, T_ENTER; TI (i));
  541.  
  542.    err_assert (self.is_valid (c), "sos_Object_List::to_succ");
  543.  
  544.    sos_List_node succ = (sos_List_node::make (c.get_current())).succ (i);
  545.    c.set_current (succ);
  546.  
  547.    sos_Bool valid = (succ != NO_OBJECT);
  548.  
  549.    TT (agg_H, T_LEAVE; TB(valid));
  550.    return (valid);
  551. } // ** to_succ **
  552.  
  553. // **************************************************************************
  554. sos_Bool sos_Object_List::to_pred (sos_Cursor c, sos_Int i)
  555. // **************************************************************************
  556. {
  557.    // Move the sos_Cursor to the previous i-th element
  558.    // The function returns FALSE if no such element exists.
  559.  
  560.    T_PROC ("sos_Object_List::to_pred");
  561.    TT (agg_H, T_ENTER; TI (i));
  562.  
  563.    err_assert (self.is_valid (c), "sos_Object_List::to_pred");
  564.  
  565.    sos_List_node pred = (sos_List_node::make (c.get_current())).pred (i);
  566.    c.set_current (pred);
  567.  
  568.    sos_Bool valid = (pred != NO_OBJECT);
  569.  
  570.    TT (agg_H, T_LEAVE; TB(valid));
  571.    return (valid);
  572. } // ** to_pred **
  573.  
  574. // ***************************    sos_List_node    **************************
  575.  
  576. // **************************************************************************
  577. void sos_List_node::insert_before (sos_List_node n)
  578. // **************************************************************************
  579. {
  580.    T_PROC ("sos_List_node::insert_before");
  581.    TT (agg_H, T_ENTER);
  582.  
  583.    sos_List_node pred = self.get_pred();
  584.  
  585.    n.set_pred (pred);
  586.    n.set_succ (self);
  587.    self.set_pred (n);
  588.    if (pred != NO_OBJECT) pred.set_succ (n);
  589.  
  590.    TT (agg_H, T_LEAVE);
  591. }  // ** insert_before **
  592.  
  593. // **************************************************************************
  594. void sos_List_node::insert_after (sos_List_node n)
  595. // **************************************************************************
  596. {
  597.    T_PROC ("sos_List_node::insert_after");
  598.    TT (agg_H, T_ENTER);
  599.  
  600.    sos_List_node succ = self.get_succ();
  601.  
  602.    n.set_pred (self);
  603.    n.set_succ (succ);
  604.    self.set_succ (n);
  605.    if (succ != NO_OBJECT) succ.set_pred (n);
  606.  
  607.    TT (agg_H, T_LEAVE);
  608. }  // ** insert_after **
  609.  
  610. // **************************************************************************
  611. void sos_List_node::remove ()
  612. // **************************************************************************
  613. {
  614.    T_PROC ("sos_List_node::remove");
  615.    TT (agg_H, T_ENTER);
  616.  
  617.    sos_List_node pred = self.get_pred();
  618.    sos_List_node succ = self.get_succ();
  619.  
  620.    if (pred != NO_OBJECT) pred.set_succ (succ);
  621.    if (succ != NO_OBJECT) succ.set_pred (pred);
  622.  
  623.    self.destroy();      // destroy the node
  624.  
  625.    TT (agg_H, T_LEAVE);
  626. }  // ** remove **
  627.  
  628. // **************************************************************************
  629. sos_List_node sos_List_node::succ (sos_Int steps)
  630. // **************************************************************************
  631. {
  632.    T_PROC ("sos_List_node::succ");
  633.    TT (agg_H, T_ENTER; TI (steps));
  634.  
  635.    sos_List_node node = self;
  636.  
  637.    for (sos_Int i = 1;
  638.         (i <= steps) AND (node != NO_OBJECT);
  639.         i++)
  640.        node = node.get_succ ();
  641.  
  642.    TT (agg_H, T_LEAVE; TI(i));
  643.    return node;
  644. }  // ** succ **
  645.  
  646. // **************************************************************************
  647. sos_List_node sos_List_node::pred (sos_Int steps)
  648. // **************************************************************************
  649. {
  650.    T_PROC ("sos_List_node::pred");
  651.    TT (agg_H, T_ENTER; TI (steps));
  652.  
  653.    sos_List_node node = self;
  654.  
  655.    for (sos_Int i = 1;
  656.         (i <= steps) AND (node != NO_OBJECT);
  657.         i++)
  658.        node = node.get_pred();
  659.  
  660.    TT (agg_H, T_LEAVE; TI(i));
  661.    return node;
  662. }  // ** pred **
  663.